package bin_tree.heap.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author yuisama
 * @date 2023/03/31 20:10
 * 最小的K个数
 **/
public class Num17_14_SmallestK {
    // 取小用大堆
    public int[] smallestK(int[] arr, int k) {
        // 1.改造JDK的最小堆为此时的最"大"堆
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i : arr) {
            queue.offer(i);
            if (queue.size() > k) {
                queue.poll();
            }
        }
        // 此时队列中保存了最小的k个数字
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = queue.poll();
        }
        return result;
    }
}